Modified Truncated Randomized Singular Value Decomposition (MTRSVD) Algorithms for Large Scale Discrete Ill-posed Problems with General-Form Regularization

摘要

In this paper, we propose new randomization based algorithms for large scalediscrete ill-posed problems with general-form regularization: ${\min} \|Lx\|$subject to ${\min} \|Ax - b\|$, where $L$ is a regularization matrix. Ouralgorithms are inspired by the modified truncated singular value decomposition(MTSVD) method which suits only for small to medium sized problems, andrandomized SVD algorithms that generate low rank approximations to $A$. We userank-$k$ truncated randomized SVD (TRSVD) approximations to $A$ by truncatingthe rank-$(k+q)$ randomized SVD (RSVD) approximations to $A$ other than thebest rank-$k$ approximation to $A$, where $q$ is an oversampling parameter. Theresulting algorithms are called modified TRSVD (MTRSVD) methods. At every step,we use the LSQR algorithm to solve the resulting inner least squares problem,which is proved to become better conditioned as $k$ increases. We present sharpbounds for the approximation accuracy of the RSVDs and TRSVDs for severely,moderately and mildly ill-posed problems, and substantially improve a knownbasic bound for TRSVD approximations. Numerical experiments show that the bestregularized solutions obtained by MTRSVD are as accurate as the bestregularized solutions obtained by the truncated generalized singular valuedecomposition (TGSVD) method, and they are at least as accurate as and can bemuch more accurate than those by some existing truncated randomized generalizedsingular value decomposition (TRGSVD) algorithms.